package codeRandomThoughts.Test113路径总和II;

import codeRandomThoughts.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;


//路径总和II二刷
public class Solution2 {

    int pathSum = 0;
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();


    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return result;
        pathSum += root.val;
        path.add(root.val);
        backtracking(root, targetSum);
        return result;
    }

    public void backtracking(TreeNode node, int targetSum) {
        //终止条件
        if (node.left == null && node.right == null) {
            if (pathSum == targetSum) {
                result.add(new ArrayList<>(path));
            }
            return;
        }

        //单层递归逻辑
        if (node.left != null) {
            pathSum += node.left.val;
            path.add(node.left.val);
            backtracking(node.left, targetSum);
            path.remove(path.size() - 1);
            pathSum -= node.left.val;
        }
        if (node.right != null) {
            pathSum += node.right.val;
            path.add(node.right.val);
            backtracking(node.right, targetSum);
            path.remove(path.size() - 1);
            pathSum -= node.right.val;
        }
    }
}
